This invention relates generally to a method and apparatus for monitoring, policing and billing of the transmission of data packet on a communications network. More specifically, this invention provides the monitoring, policing and billing in networks with timely forwarding and delivery of data packets to their destination nodes. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, are predictable, and therefore, it is possible to measure them. Consequently, such measurements are used in the monitoring, policing and billing.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real time data, like telephony and video. However, the end-to-end transport requirements and the ability to measure the actual performance of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current a synchronous networking technologies.
Monitoring, policing and billing are possible today only over circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [Balla et al., xe2x80x9cSONET: Now It""s The Standard Optical Networkxe2x80x9d, IEEE Communications Magazine, Vol. 29 No. 3, March 1989, pages 8-15] [M. Schwartz, xe2x80x9cTelecommunication Networks: Protocols, Modeling, and Analysisxe2x80x9d, Addison Wesley, Reading Mass., 1987].
Packet switching networks like IP (Internet Protocol)-based Internet and Intranets [see, for example, A.Tannebaum, xe2x80x9cComputer Networksxe2x80x9d (3rd Ed) Prentice Hall, 1996] are not designed for doing monitoring, policing and billing.
In order to facilitate the capability for monitoring, policing and billing some enhancements were proposed for P networks. Such methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [M. G. H. Katevenis, xe2x80x9cFast Switching And Fair Control Of Congested Flow In Broadband Networksxe2x80x9d, IEEE Journal on Selected Areas in Communications, SAC-5(8):1315-1326, Oct. 1987; Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989; S. J. Golestani, xe2x80x9cCongestion-Free Communication In High-Speed Packet Networksxe2x80x9d, IEEE Transcripts on Communications, COM-39(12):1802-1812, December 1991; Parekh et al., xe2x80x9cA Generalized Processor Sharing Approach To Flow Controlxe2x80x94The Multiple Node Casexe2x80x9d, IEEEIACM T. on Networking, 2(2):137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., xe2x80x9cA Scheme For Real-Time Channel Establishment In Wide-Area Networksxe2x80x9d, IEEE Journal on Selected Areas in Communication, SAC-8(4):368-379, Apr. 1990; Kandlur et al., xe2x80x9cReal Time Communication In Multi-Hop Networksxe2x80x9d, IEEE Trans. on Parallel and Distributed Systems, Vol. 5, No. 10, pp. 1044-1056, 1994]. Both of these approaches rely on manipulation of local queues by each router with little coordination with other routers. The Weighted Fair Queuing (WFQ), which typifies these approaches, is based on cyclical servicing of the output port queues where the service level of a specific class of packets is determined by the amount of time its queue is served each cycle [Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989]. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, RTP: A Transport Protocol for Real-Time Applications, IETF Request for Comment RFC1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currenty the accepted method for transporting real time streams over IP intemetworks and packet audio/video telephony based on ITU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, xe2x80x9cThe Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecturexe2x80x9d, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana, Report No. UIUCDCS-R-87-1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, xe2x80x9cIntegration Of Voice Communication On A Synchronous Optical Hypergraphxe2x80x9d, INFOCOM""88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to-point links. The two papers [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] provide an abstract (high level) description of what is called xe2x80x9cRISC-like forwardingxe2x80x9d, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine [Patterson et al., xe2x80x9cComputer Architecture: A Quantitative Approachxe2x80x9d, Morgan Kaufman Publishers, San Francisco, 1990].
In U.S. Pat. No. 5,455,701, Eng et al. discloses an apparatus for controlling a high-speed optical switching system with pipeline controller for switch control. In U.S. Pat. No. 5,418,779 Yemini et al. disclose a switched network architecture with common time reference. The time reference is used in order to determine the time in which multiplicity of nodes can transmit simultaneously over one predefined routing tree to one destination. At every time instance the multiplicity of nodes are transmitting to different single destination node.
This invention discloses a method for monitoring and policing the packet traffic in a packet switching network where the switches maintain a common time reference.
This invention enables designated points inside the network to ascertain the level of packet traffic in predefine time intervals, and control the flow of packets and bring it back to predetermined levels in cases where the traffic volume exceeds predetermined levels.
The information collected by the designated points facilitates billing for Internet services based on network usage, and identification of faulty conditions and malicious forwarding of packets that cause excessive delay beyond predetermined value.
In accordance with the present invention, a method is disclosed providing virtal pipes that carry real-time traffic over packet switching networks while guaranteeing end-to-end performance. The method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections. On the Internet the non-reserved data packet traffic is called xe2x80x9cbest effortxe2x80x9d traffic. In accordance with the present invention, the bandwidth allocated to a connection and the delay and jitter inside the network are independent. MPLS can be used by the present invention to identify virtual pipes. The packet time-stamp that is carried in the RTP header can be used in accordance with the present invention to facilitate time-based transport
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. The present invention provides real-time services by synchronous methods that utilize a time reference that is common to the switches and end stations comprising a wide area network The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning Systemxe2x80x94see, for example: http://www.utexas.eduldeptstgrg/gcraftfnotestgps/gps.html). By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom. The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standards and Technologies (NIST) (see http:www.boulder.nist.gov/timefreq) is responsible for coordinating with the International Bureau of Weights and Measures (BIPM) in Paris in maintaining UTC.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc.""s (Santa Rosa, Calif.) PCI-SG provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, xe2x80x9cNetwork Time Protocorxe2x80x9d (version 3) IETF RFC 1305]. However, the clock accuracy of NTP is not adequate for interswitch coordination, on which this invention is based.
In accordance with the present invention, the use of reserved resources is allowed by all packet traffic whenever the reserved resources are not in use.
A key difference between the synchronous optical hypergraph and the present invention is the forwarding of packets over simple point-to-point edges in this invention. The pipeline in accordance with the present invention is used for the forwarding of packets inside the network, not for switch control as in the Eng et al. patent
Although the present invention relies on time to control the flow of packets inside the network in a similar fashion as in circuit switching, there are major differences between the two approaches. In circuit switching, for each data unit (e.g., a byte) at the time it has been transmitted from its source, it is possible to predict deterministically the future times it will be transmitted from any switch along its route [Balart et al., xe2x80x9cSONET: Now It""s The Standard Optical Networkxe2x80x9d, IEEE Communications Magazine, Vol. 29 No. 3, March 1989, pages 8-15]. The time resolution of this advanced knowledge is much shorter than the data unit transmission time. On the other hand, in accordance with the present invention, for each data unit (e.g., a cell) at the time it has been transmitted from its source, it is possible to know the future time frames that this data unit will be forwarded along its route. However, the time frame, which constitutes the accuracy of this advance timing knowledge, is much larger than one data unit transmission time. For example, the transmission time of an ATM cell (53 bytes) over a gigabit per second link is 424 nanoseconds, which is 294 times smaller than a typical time frame of 125 microsecondsxe2x80x94used in one embodiment of the present invention. There are several consequences that further distinguish the present invention from circuit switching:
In accordance with the present invention, the synchronization requirements are independent of the physical link transmission speed, while in circuit switching the synchronization becomes more and more difficult as the link speed increases.
In accordance with the present invention, timing information is not used for routing, and therefore, in the Internet, for example, the routing is done using IP addresses or a tag/label.
In accordance with the present invention, the Internet xe2x80x9cbest effortxe2x80x9d packet forwarding strategy can be integrated into the system.
These and other aspects and attributes of the present invention will be discussed with reference to the following drawings and accompanying specification.